#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
	vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
		int len1 = nums1.size();
		int len2 = nums2.size();
		if (!len1 || !len2) return {};

		vector<int> res{};
		int min = len1 < len2 ? len1 : len2;
		int i = 0, j = 0;

		sort(nums1.begin(),nums1.end());
		sort(nums2.begin(), nums2.end());
		
		while (i<len1 && j<len2)
		{
			if (nums1[i] == nums2[j])
			{
				res.push_back(nums1[i]);
				i++;
				j++;
			}
			else if (nums1[i] > nums2[j])
			{
				j++;
			}
			else
			{
				i++;
			}
		}

		return res;
	}
};

int main()
{
	Solution s;
	vector<int> arr1{ 1,2,2,1 };
	vector<int> arr2{ 2};

	vector<int> res = s.intersect(arr1,arr2);
	for (auto it = res.begin();it != res.end();it++)
	{
		cout << (*it) << " ";
	}
	return 0;
}